package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * 真的nb 快速排序，说白了就是给基准数据找其正确索引位置的过程！
 *                 说白了就是给基准数据找其正确索引位置的过程！
 *                  说白了就是给基准数据找其正确索引位置的过* 8w的数据 0.021s  无解。n个数据治n-1次 8个数据合7次
 *                  ref:<a href="https://blog.csdn.net/nrsc272420199/article/details/82587933">...</a>
 *                  但我和上图的方式不一样。建议自己debug画图一下。
 */
public class QuickSorting {
    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22};
        int[] arr2 = {49, 38};
        int []arr3 = {23,46,0,8,11,18};
        quickSort(arr3, 0, arr3.length - 1);
        System.out.println(Arrays.toString(arr3));
        //costTime();
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getIndex(arr, low, high);
            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }
    }

    /**
     * 找基准最重要的方法，采用的策略是使数组第一个元素作为基准，i与j分别指向首和尾，
     * i 与 j 移动 ，互相交换
     * 到最后i == j 的时候，将基准与i交换。
     * 当时想弄一个动图演示的，但我debug是一样的呀！
     */
    private static int getIndex(int[] arr, int low, int high) {
        int i = low;
        int j = high;
        // 基准数据
        int tmp = arr[low];
        while (i < j) {
            // 当队尾的元素大于等于基准数据时,向前挪动j指针
            while (i < j && arr[j] >= tmp) {
                j--;
            }
            // 当队首元素小于等于tmp时,向前挪动i指针
            while (i < j && arr[i] <= tmp) {
                i++;
            }
            // 上面二个while循环结束，因为分别碰到了比基准小 与 碰到了比基准大的元素。
            // 然后进行一个交换。
            // 这里可以不用判断 i 是否小于j  如果i==j 再交换，交换的内容都是一样的，增加了if语句可能会造成更多的时间。
            swap(arr,i,j);
        }
        // 跳出循环时i和j相等,此时的i或j就是tmp的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是tmp,需要互相交换pivot（第一个元素） 和 应该去的地方
        swap(arr,low,i);
        return i; // 返回tmp的正确位置
    }

    // 抽取交换方法
    public static void swap(int[]arr,int i,int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    /**
     *  测试八万的数据
     */
    public static void costTime() {
        int[] arrays3 = new int[8000000];
        Random random2 = new Random();
        for (int i = 0; i < arrays3.length; i++) {
            arrays3[i] = random2.nextInt(8000000);
        }
        long startTime = System.currentTimeMillis();
        quickSort(arrays3,0, arrays3.length-1);   // 正规的插入，有值的后移
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间优化时间为：" + (endTime - startTime)*0.001 + "s"); //输出程序运行时间
    }
}
